//2009/08/07 16:23:11
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
// The brute force way waste soooo much time;
/*
class TennisRallies
{
public:
    int howMany(int numLength, vector <string> forbidden, int allowed)
    {
        int count = 0;
        for (int i=0; i < (1<<numLength); i++)
        {
			//generate a binary string, 0->c and 1->d; 000.... through 111...;
			string s;
			for(int digit=1, j=0; digit < (1<<numLength); digit*=2, j++)
			{
				if((digit & i) == 0) s = 'c' + s;
				else s = 'd' + s;
			}
			int forb = 0;
			for(int j=0; j<s.size(); j++)
			{
				for(int k=0; k<forbidden.size(); k++)
				{
					if(s.substr(j, forbidden[k].size()).compare(forbidden[k]) == 0) forb ++;
				}
			}
			if(forb < allowed) count ++;
        }
		return count;
    }
};
*/

class TennisRallies
{
public:
    int howMany(int numLength, vector<string> forbidden, int allowed)
    {
		return recursive(0, numLength, "", forbidden, allowed);
    }
private:
    int recursive(int index, int numLength, string current, vector<string> forbidden, int allowed)
    {
        if (index == numLength) return 1;
		int count = 0;
		for(char str = 'c'; str <= 'd'; str++)
		{
			int newallowed = allowed;
			string newstring = current + str;
			for(int i=0; i<forbidden.size(); i++)
			{
				if(newstring.size() >= forbidden[i].size())
				{
					if(newstring.substr(newstring.size() - forbidden[i].size(),forbidden[i].size()).compare(forbidden[i]) == 0)
						newallowed --;
				}
			}
			if(newallowed <= 0) continue;
			count += recursive(index + 1, numLength, newstring, forbidden, newallowed);
		}
		return count;
    }
};

